class Prime {
  // 构造函数
  constructor(graph) {
    this.graph = graph // 这个图的元素是[from,to,cost]
    this.pq = new myPriorityQueue() // 优先级队列
    this.n = graph.length // 这个的长度
    this.inMst = new Array(this.n).fill(false) // 类似visited数组的作用 记录那些节点已经成为最小生成树的一部分
    this.inMst[0] = true // 从0节点开始切分
    this.cut(0) // 从0开始切分
    this.weightSum = 0 // 记录最小生成树的权重和
    while (this.pq.items.length) { // 当优先级队列不为空
      let edge = this.pq.dequeue() // 弹出优先级队列的头部
      let to = edge.element[1] // 要去的 是edge里面element的1 和element的2
      let weight = edge.element[2] // 权重
      if (this.inMst[to]) {
        // 如果这个已经在最小生成树中了
        continue // 调过探测这条边
      }
      // 如果没有探测过这条边 进行下一步的计算
      this.weightSum += weight
      this.inMst[to] = true // 记录探测过这条边
      this.cut(to) // 进行下一次的探测
    }
  }
  cut (s) { // 接受一个节点作为参数
    for (let edge of this.graph[s]) {
      // 遍历这个节点对应的图的每一个边
      let to = edge[1]
      if (this.inMst[to]) {
        continue // 如果已经访问过 就调过
      }
      this.pq.enqueue(edge, edge[2]) // 否则将这条边加入横切边队列 权重是第三个值
    }
  }
  // 最小生成树的权重和
  getWeightSum () {
    return this.weightSum
  }
  // 判断最小生成树是否包含图中的所有节点
  allConnected () {
    for (let i = 0; i < this.inMst.length; i++) {
      if (!this.inMst[i]) {
        return false // 如果有没被访问过的 就返回false
      }
    }
    // 最后都访问过 就返回true
    return true
  }
}
//封装优先级队列，priority越小，优先级越高
function myPriorityQueue () {
  //存放每一个插入元素QueueElement
  this.items = [];
  //定义内部类--封装插入元素
  function QueueElement (element, priority) {
    this.element = element;
    this.priority = priority;
  }
  //实现插入操作
  myPriorityQueue.prototype.enqueue = function (element, priority) {
    var qe = new QueueElement(element, priority);
    if (this.items.length === 0) {
      this.items.push(qe);
    } else {
      var flag = false; //记录元素是否插入，没有就插入到items最后
      for (var i = 0; i < this.items.length; i++) {
        if (priority < this.items[i].priority) {
          this.items.splice(i, 0, qe);
          flag = true;
          break;
        }
      }
      if (!flag) {	//没有就插入到items最后
        this.items.push(qe);
      }
    }
  }

  //2.将元素从队列中移除
  myPriorityQueue.prototype.dequeue = function () {
    return this.items.shift();
  }
  //3.查看队列中第一个元素
  myPriorityQueue.prototype.front = function () {
    return this.items[0];
  }
  //4.查看队列是否为空
  myPriorityQueue.prototype.isEmpty = function () {
    return this.items.length === 0;
  }
  //5.查看队列中元素的个数
  myPriorityQueue.prototype.size = function () {
    return this.items.length;
  }
  //6.toString
  myPriorityQueue.prototype.toString = function () {
    var result = '';
    for (var i = 0; i < this.items.length; i++) {
      result += this.items[i].element + '---' + this.items[i].priority + ' ';
    }
    return result;
  }
}




